DAY 11 試題

問題描述

給定一個包含 n 個不同數字的陣列 nums，數字範圍在 [0, n] 之間，其中正好缺少一個數字，請找出這個缺少的數字。

範例 1：

• 輸入: nums = [3,0,1]
• 輸出: 2
• 解釋: 共有 3 個數字，範圍是 [0, 3]，缺少的數字是 2。

範例 2：

• 輸入: nums = [0,1]
• 輸出: 2
• 解釋: 共有 2 個數字，範圍是 [0, 2]，缺少的數字是 2。

範例 3：

• 輸入: nums = [9,6,4,2,3,5,7,0,1]
• 輸出: 8
• 解釋: 共有 9 個數字，範圍是 [0, 9]，缺少的數字是 8。

解題思路

在這道題中，我們需要找出範圍 [0, n] 中缺失的數字。這類問題有多種解法，其中最常見的兩種方法是：

1. 數學總和公式解法
2. XOR 解法

方法一：數學總和公式

這種方法使用的是數學中關於等差數列的求和公式：sum(n)= (n×(n+1)) / 2
首先，計算範圍 [0, n] 中所有數字的理論總和。然後，再將陣列中的所有數字相加，兩者的差即為缺失的數字。

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int expectedSum = n * (n + 1) / 2;
        int actualSum = 0;
        for (int num : nums) {
            actualSum += num;
        }
        return expectedSum - actualSum;
    }
};

時間與空間複雜度

• 時間複雜度: O(n)，需要遍歷一次陣列來計算總和。
• 空間複雜度: O(1)，只使用了常數的空間。

方法二：XOR 解法

XOR (異或) 運算具有對稱性，即a⊕a=0，而且對於任何數字x，有x⊕0=x。
利用這個特性，我們可以將範圍 [0, n] 與陣列中的數字進行 XOR，最後剩下的結果就是缺失的數字。

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int missing = nums.size();
        for (int i = 0; i < nums.size(); i++) {
            missing ^= i ^ nums[i];
        }
        return missing;
    }
};

方法比較

1. 數學總和公式 是一個非常直觀的解法，利用等差數列求和公式來解決問題。在計算範圍總和與實際總和之後，兩者的差即為缺失的數字。這個方法的優點是易於理解，缺點是可能會出現整數溢出的問題，特別是當數字範圍非常大的時候。

2. XOR 解法 是一個較為高效且巧妙的解法。利用 XOR 的交換律和結合律，將範圍內的數字與陣列中的數字進行異或運算，最終可以抵消掉所有成對的數字，剩下的即為缺失的數字。這個方法的優點是不會出現整數溢出的問題，並且空間複雜度更低。

總結

這道題的核心在於如何有效地處理缺失數字的問題。兩種解法中，數學總和方法基於等差數列的總和計算，而 XOR 解法則利用了 XOR 運算的特性進行高效計算。在面對大範圍數字時，XOR 方法的優勢更為明顯，因為它不僅避免了溢出問題，還能保持 O(1) 的空間複雜度。

以上是第十一天的自學內容分享，謝謝大家。